Università degli studi del Piemonte Orientale "Amedeo Avogadro"
II Facoltà di Scienze MFN
Sede di Alessandria
Corso di Laurea in Informatica

Esercizi per il corso di
Sistemi Operativi I
A.A. 1998/99 - Docente: Giuliana Franceschinis
  
  Esercizi Introduttivi
  Esercizi sulla gestione dei processi
  Esercizi di Programmazione concorrente
  Esercizi sullo scheduling della CPU
  Esercizi sul deadlock
  Esercizi sulla gestione della memoria e sulla memoria virtuale
  Esercizi sul file system e gestione dei dischi
  Esercizi sui meccanismi di protezione
Pagina in allestimento (ultima modifica 22/01/99)
Esercizi Introduttivi
(1)
A che cosa serve un sistema operativo ?
Suggerimento: vi sono più risposte possibili, corrispondenti a diversi punti di vista, per esempio quello dell'utente (che vorrà un sistema facile da usare e con tempi di risposta brevi), o quello di chi fa pagare gli utenti per l'utilizzo delle risorse di calcolo (il cui obiettivo sarà un utilizzo intenso delle risorse).
(2)
Qual è il principale vantaggio della multiprogrammazione? Quali sono i problemi (in termini di possibili interferenze fra programmi contemporaneamente in esecuzione) introdotti dalla multiprogrammazione?
(3)
Definire in poche parole un sistema operativo time-sharing. In quale situazione può risultare più conveniente utilizzare un sistema time-sharing anzichè un personal computer o una workstation completamente a disposizione dell'utente ?
(4)
Un sistema operativo ben progettato deve garantire che un programma non possa inavvertitamente (o volontariamente) compromettere il funzionamento degli altri programmi nel sistema. Descrivere quale tipo di supporto hardware può supportare la protezione della CPU (un processo non deve poter occupare indefinitamente la CPU), la protezione della memoria (un processo non deve poter accedere e tanto meno modificare i dati e/o il codice di un altro processo), la protezione dei dispositivi di I/O (un processo non deve poter eseguire operazioni illegali di I/O, per esempio andare a scrivere su settori del disco dove sono contenute informazioni cruciali per la gestione del file system o dati di altri utenti).
(5)
Spiegare la differenza fra interrupt e trap (fare alcuni esempi concreti di eventi che causano interrupt e di eventi che causano trap). Cosa succede quando si verifica un interrupt o una trap?
(6)
Elencare le principali componenti di un sistema operativo ed elencare per ciascuna di esse le principali funzioni svolte.
(7)
Cos'è una system call?
(8)
Descrivere alcuni modi alternativi di strutturare un sistema operativo discutendo pregi e difetti di ciascun approccio.

Esercizi sulla gestione dei processi
(1)
Cos'è un processo? Quali sono i possibili stati in cui si può trovare un processo e quali sono gli eventi che causano il passaggio da uno stato all'altro? (illustrare le possibili transizioni di stato attraverso un diagramma degli stati).
(2)
Che cos'è il process control block (PCB)? Elencare quali informazioni sono contenute nel PCB.
(3)
Che cos'è il context switch? Quale componente del sistema operativo decide quale processo diventerà running al momento del context switch? Quale componente del sistema operativo effettua le operazioni necessarie per realizzare il context switch?
(4)
Che differenza c'è fra un processo e un thread?

Esercizi di Programmazione concorrente (Es.1,Es.2,Es.3 Es.4, Es.5, Es.6, Es.7, Es.8, Es.9, Es.10)
(1)
Fare un esempio di situazione di corsa critica (race condition). I problemi di corsa critica si manifestano sempre ad ogni esecuzione concorrente dei processi coinvolti?
(2)
Generalizzare l'algoritmo di Peterson (Fig. 2-8 del libro di testo) al caso di n>2 processi.
Suggerimento: Si puo` realizzare simulando il metodo usato per servire i clienti in un negozio solitamente affollato, cioè chi vuole essere servito preleva un numero da un distributore (il processo i segnala così di essere intenzionato ad entrare in sezione critica scrivendo il numero prelevato in un vettore number alla posizione i) e il servizio viene quindi accordato in ordine di numero prelevato (entra in sezione critica il processo che scandendo il vettore number non trova nessuno con numero maggiore al suo).
(3)
Supponiamo che anzichè disporre della istruzione Test_and_set una CPU abbia invece una istruzione (atomica) di Swap così definita:
    
procedure Swap(var a,b:boolean)    
var temp: boolean;    
begin    
  temp:=a;    
  a:=b;    
  b:=temp;    
end    
come si può implementare la mutua esclusione tramite la swap? E` ammesso il busy waiting. (La soluzione è simile a quella che fa uso della test_and_set).
(4)
Il problema dei lettori e degli scrittori prevede che m processi lettori ed n processi scrittori possano richiedere di accedere a dati condivisi (per esempio contenuti in un data base). Si permette l'accesso simutaneo da parte di più lettori mentre l'accesso da parte di uno scrittore deve essere eseguito in mutua esclusione con qualsiasi altro processo, sia esso lettore o scrittore. Si implementi una soluzione al problema dei lettori e scrittori in un ambiente a memoria condivisa utilizzando i semafori oppure utilizzando il costrutto monitor.
Attenzione: Ciò che si chiede di realizzare sono quattro procedure: inizio_lettura,fine_lettura, inizio_scrittura,fine_scrittura, supponendo che ogni processo esegua la procedura inizio_operazione prima di procedere ad effettuare l'operazione di lettura/scrittura, ed esegua la procedura fine_operazione dopo aver completato l'operazione.
(5)
Se al precedente esercizio aggiungiamo i seguenti requisiti (che servono ad evitare la starvation dei processi):
  • un nuovo lettore non può acquisire la risorsa se vi è uno scrittore in attesa
  • tutti i lettori sospesi al termine di una scrittura hanno priorità sul successivo scrittore
come deve essere modificata la soluzione al problema tramite monitor?
(6)
Come è possibile implementare il costrutto monitor su un sistema che disponga solo delle primitive semaforiche?
Osservazione: La soluzione dipende dall'eventuale vincolo sull'uso della cond.signal. Se tale istruzione può comparire solo come ultima istruzione nelle procedure del monitor la soluzione è più semplice.
(7)
Come si possono implementare le primitive semaforiche (up/down) tramite un monitor? Si semplifica l'implementazione se ci si limita al caso dei semafori binari anzichè considerare il caso più generale
(8)
È possibile implementare correttamente la soluzione al problema di sincronizzazione fra un processo produttore ed un consumatore disponendo solo di semafori binari (ovvero semafori che possono solo assumere i valori 0 e 1) ?
(9)
I costrutti linguistici fork-join e cobegin-coend permettono di creare processi: in cosa differiscono? Hanno la stessa potenza espressiva? Provare a realizzare con i due costrutti i seguenti grafi di precedenza:
(10)
Realizzare un processo buffer di N posizioni (ovvero capace di contenere al più N messaggi) facendo uso di send sincrone e receive bloccanti, ed utilizzando comandi con guardie.

Esercizi sullo scheduling della CPU
(1)
Si consideri il seguente insieme di processi: ad ognuno è associata la durata del prossimo CPU-burst e la priorità.
    
PROC  CPU-burst  PRIOR    
P1      10         3    
P2       1         1    
P3       2         3    
P4       1         4    
P5       5         2    
Si suppone che i processi siano arrivati tutti al tempo 0 nell'ordine del corrispondente indice. Si illustri attraverso diagrammi di Gantt l'ordine di esecuzione dei processi utilizzando gli algoritmi FCFS, SJF, priorità (numeri piccoli = priorità alta) e Round Robin con quanto di tempo di 1 unità Calcolare in ciascun caso il tempo di turnaround e il tempo di attesa di ogni processo. Quale algoritmo permette di ottenere il minor tempo medio di attesa?
(2)
Si consideri il seguente algoritmo di scheduling basato su priorità dinamiche (ovvero che cambiano nel tempo). In questo sistema valori numerici più grandi corrispondono a priorità più alte. Quando un processo è nella ready queue, la sua priorità cambia con un tasso x; quando invece è running la sua priorità cambia con un tasso y. Quando un processo entra nella ready queue gli viene assegnata priorità 0. Assegnando opportuni valori ai parametri x ed y è possibile ottenere diversi algoritmi di scheduling. Quali algoritmi di scheduling si ottengono nei due casi seguenti?
  • y > x > 0
  • x < y < 0
Suggerimento: La priorità di un processo ready al tempo t+dt (assumendo che sia rimasto ready in tutto l'intervallo (t,t+dt)) è prio(t+dt) = prio(t) + x dt, per un processo running invece sarà prio(t+dt) = prio(t) + y dt. Si suggerisce di provare a rappresentare in un grafico l'andamento nel tempo delle priorità dei processi ready e running.
(3)
(4)

Esercizi sul deadlock
(1)
Si consideri un sistema che possiede 4 risorse tutte dello stesso tipo. Supponiamo che siano in esecuzione tre processi che usano tali risorse e che possono al massimo richiedere 2 risorse ciascuno. Dimostrare che i tre processi non possono mai trovarsi in uno stato di deadlock.
(2)
Si supponga di aver verificato, utilizzando l'algoritmo del banchiere per 2 tipi di risorsa, che un sistema in cui sono attivi tre processi P1, P2, P3 che condividono le risorse di tipo A,B,C e D, si trova in uno stato sicuro sia rispetto alle risorse di tipo A e B, sia rispetto alle risorse di tipo C e D (ovvero, l'algoritmo è stato fatto prima eseguire considerando solo le risorse di tipo A e quelle di tipo B, e poi considerando solo le risorse di tipo C e quelle di tipo D). Si può concludere che il sistema sia in uno stato sicuro rispetto a tutti e quattro i tipi di risorsa? Giustificare la risposta (anche con un esempio).

Esercizi sulla gestione della memoria e sulla memoria virtuale
(1)
Supponiamo che il meccanismo hardware di traduzione degli indirizzi preveda la presenza di un registro base RB e di un registro limite RL, per cui ogni indirizzo logico viene tradotto secondo il seguente schema:
if indirizzo_logico > RL then TRAP
   else indirizzo_fisico = indirizzo_logico + RB
Quale delle seguenti tecniche di gestione della memoria può essere implementata?
  • partizioni fisse
  • partizioni variabili
  • paginazione
  • segmentazione paginata
(2)
Si consideri un sistema paginato con tabella delle pagine memorizzata in memoria centrale. Si supponga che lo spazio degli indirizzi virtuali sia di 16 pagine di 512 parole, la memoria fisica sia di 64 frame, e ogni descrittore di pagina logica nella tabella delle pagine occupi una parola.
  • Quanti bit compongono un indirizzo logico (o virtuale) ?
  • Quanti bit compongono un indirizzo fisico?
  • Nell'ipotesi che il sistema in esame abbia un grado di multiprogrammazione costante uguale ad n, calcolare l'overhead di memoria dovuto alla paginazione (ovvero la quantità totale di memoria utilizzata per mantenere le tabelle delle pagine più la memoria sprecata a causa della frammentazione).
(3)
Si supponga di avere una memoria fisica di dimensione 4096Kbyte, e di utilizzare uno schema di gestione a partizioni variabili in cui l'unità minima di allocazione della memoria è di 64 byte (ovvero lo spazio di memoria viene allocato in multipli di 64 byte). Si considerino le seguenti strutture per mantenere traccia dello spazio libero disponibile:
  • una bit map
  • una lista linkata in cui ogni nodo rappresenta una partizione libera; i nodi della lista sono costituiti da due campi: (dimensioni della partizione, puntatore alla partizione successiva) e sono memorizzati nei primi byte della partizione che rappresentano.
Per ciascuna di queste due alternative si valuti la quantità di spazio che è necessario riservare per mantenere la struttura e si mettano in luce vantaggi e svantaggi. Quale di queste alternative può essere usata vantaggiosamente per gestire lo spazio libero su disco?
(4)
Data la seguente stringa di riferimenti alle pagine di un processo
0, 1, 2, 1, 3, 4, 1, 2, 0, 1
Calcolare il numero di page fault, indicando a fronte di ciascun riferimento l'eventuale vittima, utilizzando
  • l'algoritmo FIFO con una memoria fisica di 4 frames
  • l'algoritmo della seconda scelta con una memoria fisica di 4 frames
  • l'algoritmo LRU con una memoria fisica di 3 o 4 frames
(5)
Si consideri la seguente sequenza di riferimenti in memoria nel caso di un programma di 460 parole:
10, 11, 104, 170, 73, 309, 185, 245, 246, 434, 458, 364
  • Si determini la stringa dei riferimenti supponendo che la dimensione delle pagine sia di 100 parole. Sapendo che la memoria principale a disposizione per il programma è di 200 parole e che si utilizza come algoritmo di rimpiazzamento il FIFO, determinare quanti page fault si verificheranno.
  • Si ripeta il precedente esercizio supponendo che la dimensione delle pagine sia ridotta a 50 parole mentre la dimensione della memoria a disposizione e l'algoritmo di rimpiazzamento rimangano invariati.
Osservazione: normalmente la dimensione delle pagine è una potenza di due (sapete spiegare perchè?). In questo esercizio si è usata una dimensione diversa per facilitare il calcolo delle pagine a partire dagli indirizzi indicati.
(6)
In un sistema che usa uno schema di gestione della memoria a partizioni variabili, la lista delle partizioni libere contiene, nell'ordine, una partizione da 100K, una da 500K, una da 200K, una da 300K e una da 600K. Come verrebbero allocate le seguenti richieste (sottoposte al sistema nell'ordine indicato) e utilizzando gli algoritmi First fit, Best fit e Worst fit?
212K, 417K, 112K e 426K
Si consideri un sistema che usa la paginazione su richiesta. Sono state rilevate le seguenti utilizzazioni medie delle risorse del sistema
  • U(CPU) = 20%
  • U(DISCO) = 97.7% (si tratta del disco a supporto della paginazione)
  • U(I/O DEVICES) = 5%
Quali dei seguenti interventi possono migliorare l'utilizzo della CPU, e perchè?
  • installare una CPU più veloce
  • installare un disco più grande a supporto della paginazione
  • incrementare il livello di multiprogrammazione
  • decrementare il livello di multiprogrammazione

Esercizi sul file system e gestione dei dischi
(1)
In una organizzazione dell'allocazione dei file simile a quella adottata in UNIX vi sono 14 puntatori nel descrittore di file (mantenuto in memoria durante l'accesso al file) di cui
  • 12 puntatori diretti a blocchi
  • 1 puntatore indiretto a blocchi
  • 1 puntatore doppiamente indiretto a blocchi
Se la dimensione di un blocco è 1Kb, e un puntatore occupa 4 bytes, qual è la dimensione massima di un file per il quale non sono necessari accessi aggiuntivi per accedere a qualunque blocco? Qual è la dimensione massima di un file? Quanti accessi aggiuntivi sono necessari per accedere al byte alla posizione 300K?
(2)
  • Descrivere i tre tipi di allocazione dei file su disco: contigua, a lista linkata, con blocco indice.
  • Quali tipi di frammentazione caratterizzano ciascuna delle suddette organizzazioni?
  • Quale tipo di accesso a file (diretto o sequenziale) è efficiente nelle diverse organizzazioni?
  • Quale vantaggio comporta l'uso di una FAT (File Allocation Table) rispetto all'organizzazione a blocchi linkati ?
(3)
Quali sono le tre componenti del tempo di accesso a disco? Quale di questi tempi tende ad essere dominante? È più conveniente effettuare pochi trasferimenti di blocchi di grosse dimensioni oppure molti trasferimenti di blocchi di piccole dimensioni?
(4)
Cosa è un pathname relativo? E un pathname assoluto ? Cosa è un link ? In una organizzazione a grafo (aciclico) delle directory, per quale motivo può non essere conveniente mantenere le informazioni relative alla dimensione e alla localizzazione del file su disco all'interno della entry corrispondente nella directory?
(5)
Dato un disco a testa mobile con 200 tracce (numerate da 0 a 199), con richiesta in corso di servizio alla traccia 143, ultima richesta precedentemente servita alla traccia 125 e con la seguente coda di richieste:
140, 37, 12, 95, 180, 57, 12
Indicare la sequenza di spostamenti della testina per una schedulazione SSF (Shortest Seek First), algoritmo dell'ascensore, algoritmo dell'ascensore nella variante circolare

Esercizi sui meccanismi di protezione
(1)
Cosa è un dominio? Come vengono rappresentati i diritti di accesso ad un dato oggetto nella matrice dei diritti di accesso? Quali sono i domini in UNIX? Si facciano degli esempi di cambiamento di dominio in UNIX. Si faccia un esempio di comando UNIX che modifica la matrice degli accessi.
(2)
Si descrivano differenze, vantaggi e svantaggi per la protezione ad access list e a capability list. UNIX usa un tipo di protezione a capability list o ad access list?

Torna alla pagina del Corso di Sistemi Operativi I
Torna alla pagina del Corso di Laurea in Informatica
Torna alla pagina della II Facoltà di scienze MFN